package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC130 {
    public void solve(char[][] board) {
        if (board.length == 0) return;

        int m = board.length;
        int n = board[0].length;
        // 将首列和末列的 O 与 dummy 连通
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O')
                DFSTravelAndSet(board, i, 0);
            if (board[i][n - 1] == 'O')
                DFSTravelAndSet(board, i, n - 1);
        }
        // 将首行和末行的 O 与 dummy 连通
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O')
                DFSTravelAndSet(board, 0, j);
            if (board[m - 1][j] == 'O')
                DFSTravelAndSet(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }

        return;
    }


    public void DFSTravelAndSet(char[][] board, int x, int y) {
        if (board[x][y] == 'X' || board[x][y] == '#') {
            return;
        }

        board[x][y] = '#';
        // trave four direction

        if (x - 1 >= 0) {// up
            DFSTravelAndSet(board, x - 1, y);
        }

        if (x + 1 <= board.length - 1) {// down
            DFSTravelAndSet(board, x + 1, y);
        }

        if (y + 1 <= board[0].length - 1) {// right
            DFSTravelAndSet(board, x, y + 1);
        }

        if (y - 1 >= 0) {// left
            DFSTravelAndSet(board, x, y - 1);
        }
    }


    public static void main(String[] args) {
        LC130 an = new LC130();
        char[][] arr = {
                {
                        'X', 'X', 'X', 'X'
                },
                {
                        'X', 'O', 'O', 'X'
                },
                {
                        'X', 'X', 'O', 'X'
                },
                {
                        'X', 'O', 'X', 'X'
                },


        };
        an.solve(arr);
    }
}
